#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <assert.h>

#include "include/array_generator.h"
#include "include/array_help.h"

typedef struct Bound { 
    int lt; 
    int gt; 
} Bound; 

int partition(int arr[], int l, int r); 
int partition2Ways(int arr[], int l, int r); 
Bound partition3Ways(int arr[], int l, int r); 

// 快速排序是一个随机算法， 使用复杂度期望进行评估复杂度
void sort(int arr[], int l, int r) {
    if (l >= r) return;

    int p = partition(arr, l, r); 
    sort(arr, l, p - 1); 
    sort(arr, p + 1, r); 
}

// 单路快速排序，排序之前以n的复杂度shuffle一下，可以避免顺序数组退化问题
// 随机化， 单路快速排序不能解决数据样本都是重复元素的情况导致的退化 => 双路快速排序
int partition(int arr[], int l, int r) {
    int pivot = l;
    int j = l;
    // 循环不变量：[l + 1, j] < v,  [j + 1, i - 1] > v, 
    // 每次处理当前i位置的元素，循环未结束时，应满足这个性质
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < arr[pivot]) {
            Swap(arr + (j + 1), arr + i, sizeof(int)); 
            j++;
        }
    }
    Swap(arr + j, arr + pivot, sizeof(int)); 
    return j; 
}

// 双路快速排序, 虽然解决了重复元素数据样本的问题,但还是冗余很多无效交换的步骤
// 三路快速排序可以解决 
void sort2Ways(int arr[], int l, int r) {
    if (l >= r) return;

    int part = partition(arr, l, r); 
    sort2Ways(arr, l, part - 1);
    sort2Ways(arr, part + 1, r); 
}

int partition2Ways(int arr[], int l, int r) {
    int pivot = l;
    int i = l + 1;
    int j = r; 

    while (i <= j){
        while (arr[i] <= arr[pivot] && i <= j) i++;
        while (arr[j] >= arr[pivot] && i <= j) j++;
        Swap(arr + i, arr + j, sizeof(int));
        i++;
        j++;
    }

    Swap(arr + pivot, arr + j, sizeof(int )); 
    return j; 
}

// 三路快速排序
void sort3Ways(int arr[], int l, int r) {
    if (l >= r) return;

    Bound b = partition3Ways(arr, l, r);
    sort3Ways(arr, l, b.lt);
    sort3Ways(arr, b.gt, r); 
}

// TODO 三路快速排序，每次遍历整理数组，分成三段  >v  =v  <v   
Bound partition3Ways(int arr[], int l, int r) {
    Bound bound;
    return bound; 
}

// 快速排序
int main(int argc, char *argv[]) {
    int len = 1000000; 
    // int len = 100;
    // int arr[len];  // 大数据量需要在堆上分配，栈上分配报段错误  Segmentation fault
    int* arr = (int*)malloc(len * sizeof(int)); 
    GenRandomArray(arr, len, len); 
    // PrintIntArray(arr, len); 
    sort2Ways(arr, 0, len - 1); 
    // PrintIntArray(arr, len); 
    printf("isSorted = %d\n", IsSorted(arr, len)); 
    return 0; 
}

// 1亿随机样本，快速排序耗时 
// real    1m9.126s
// user    1m8.890s
// sys     0m0.171s